P1769 淘汰赛制

与题目定义有些不同,nn表示人数,mm表示淘汰赛轮数。题目显然输入的是mm,根据它算出nn。为了方便2进制计算,编号从00~n1n-1。最后答案加1即可。同时,比赛胜败概率为了方便先除以100,用doubledouble计算。

现在考虑如何计算答案,设a[i][j]a[i][j]iijj的胜率,f[i][j]f[i][j]为第iijj胜出的概率。那么有:

f[i][j]=kf[i1][j]×f[i1][k]×a[j][k]f[i][j]= \sum_{k} f[i-1][j] \times f[i-1][k] \times a[j][k]

当然,kk必须保证可能在第ii轮与jj比赛,我们可以用位运算实现。

graph _2_.png

我们会发现,在第ii轮的比赛中,只有二进制下ii位不同(输了的人不可能和赢的人再比一场),才有可能比赛,用位运算实现就是:

((j>>(i1))1)==(k>>(i1))( ( j >> ( i - 1 ) ) \oplus 1 ) == ( k >> ( i - 1 ) )

那么,暴力转移即可,最后,统计dp[m][i]dp[m][i]中的最大值,输出ii

#include <cstdio>
#include <cstring>

const int MAXN = 1 << 10;
int n , m, dex;
double f[ 15 ][ MAXN + 5 ] , a[ MAXN + 5 ][ MAXN + 5 ];

int main( ) {
    scanf("%d",&m);
    n = ( 1 << m ) - 1;
    for( int i = 0 ; i <= n ; i ++ )
        for( int j = 0 ; j <= n ; j ++ )
            scanf("%lf",&a[ i ][ j ]) , a[ i ][ j ] /= 100;
    
    for( int i = 0 ; i <= n ; i += 2 ) {
        f[ 1 ][ i ] = a[ i ][ i + 1 ];
        f[ 1 ][ i + 1 ] = a[ i + 1 ][ i ];
    }
    for( int i = 2 ; i <= m ; i ++ )
        for( int j = 0 ; j <= n ; j ++ )
            for( int k = 0 ; k <= n ; k ++ )
                if( ( ( ( j >> ( i - 1 ) ) ^ 1 ) == ( k >> ( i - 1 ) ) ) )
                    f[ i ][ j ] += f[ i - 1 ][ j ] * f[ i - 1 ][ k ] * a[ j ][ k ];
    double Ans = 0;
    for( int i = 0 ; i <= n ; i ++ )
        if( f[ m ][ i ] > Ans ) Ans = f[ m ][ dex = i ];
    printf("%d\n",dex + 1);
    return 0;
}